public class LongestSubsequence {


    public static void main(String[] args) {
        LongestSubsequence longestSubsequence = new LongestSubsequence();
        System.out.println(longestSubsequence.longestSubsequence("1001010", 5));
    }

    public int longestSubsequence1(String s, int k) {
        char[] chars = s.toCharArray();
        int one = -1;
        int end = 0;
        int sum = 0;
        int ans = 0;
        while (end < s.length()) {
            int temp = chars[end] == '1' ? 1 : 0;
            if (one == -1 && temp == 1) one = end;
            sum = (sum << 1) + temp;
            if (sum > k) {
                int index = one + 1;
                while (index < end) {
                    if (chars[index] == '1') {
                        break;
                    }
                    ++index;
                }
                sum -= 1 << (end - one);
                one = index == end ? temp == 1 ? index : -1 : index;
                ++end;
            } else {
                ++end;
                ++ans;
            }
        }
        return ans;
    }

    public int longestSubsequence(String s, int k) {
        char[] chars = s.toCharArray();
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            if (chars[i] == '0') {
                ++ans;
            }
        }
        int sum = 0;
        for (int i = s.length() - 1; i >= Math.max(0, s.length() - 31); i--) {
            if (chars[i] == '1') {
                sum += (1 << (s.length() - 1 - i));
                if (sum <= k) {
                    ++ans;
                } else return ans;
            }
        }
        return ans;
    }
}
